#pragma once
#include <vector>
#include "Utils.h"
#include <memory>
#include "SharedPtr.h"

template<typename T>
struct Node
{
	Node(T value)
		: data(new T(value))
	{
	}
	Node* next;
	SharedPtr<T> data;
};

template<typename T>
class LockFreeStack
{
public:
	LockFreeStack()
		: m_nodeHead(NULL)
		, toBeDeleted(NULL)
		, m_threadsInPop(0)
	{
	}

	~LockFreeStack()
	{
		DeleteNodes(toBeDeleted);
		DeleteNodes(m_nodeHead);
	}

	void Push(const T& data);
	SharedPtr<T> Pop();

private:
	void ChainPendingNodes(Node<T>* first, Node<T>* last);
	void ChainPendingNode(Node<T>* n);
	void ChainPendingNodes(Node<T>* nodes);
	void TryToDelete(Node<T>* old_head);
	void DeleteNodes(Node<T>* nodes);

private:
	Node<T>* m_nodeHead;
	Node<T>* toBeDeleted;
	volatile int m_threadsInPop;
};

template<typename T>
void LockFreeStack<T>::Push(const T& data)
{
	Node<T>* newNode = new Node<T>(data);
	do 
	{
		newNode->next = m_nodeHead;
	}
	while(!CompareAndExchangeWeak<Node<T>*>(&m_nodeHead, newNode->next, newNode));
}

template<typename T>
SharedPtr<T> LockFreeStack<T>::Pop()
{
	++m_threadsInPop;
	Node<T>* oldHead = NULL;
	do
	{
		oldHead = m_nodeHead;
		if (oldHead == NULL)
		{
			return NULL;
		}
        // uncomment it for getting memory delete error
		//Sleep(1);
	}
	while(!CompareAndExchangeWeak<Node<T>*>(&m_nodeHead, oldHead, oldHead->next));

	SharedPtr<T> result(oldHead ? oldHead->data : NULL);
	TryToDelete(oldHead);
	return result;
}

template<typename T>
void LockFreeStack<T>::DeleteNodes(Node<T>* nodes)
{
	while(nodes)
	{
		Node<T>* next = nodes->next;
		delete nodes;
		nodes = next;
	}
}

template<typename T>
void LockFreeStack<T>::TryToDelete(Node<T>* oldHead)
{
	if(m_threadsInPop == 1)
	{
		Node<T>* nodesToDelete = reinterpret_cast<Node<T>*>(CompareAndExchangeReturn<Node<T>*>(&toBeDeleted,
																							   toBeDeleted,
																							   NULL));
		if(!--m_threadsInPop)
		{
			DeleteNodes(nodesToDelete);
		}
		else if(nodesToDelete)
		{
			ChainPendingNodes(nodesToDelete);
		}
		delete oldHead;
	}
	else
	{
		ChainPendingNode(oldHead);
		--m_threadsInPop;
	}
}

template<typename T>
void LockFreeStack<T>::ChainPendingNodes(Node<T>* nodes)
{
	Node<T>* last = nodes;
	while(Node<T>* next = last->next)
	{
		last = next;
	}
	ChainPendingNodes(nodes, last);
}

template<typename T>
void LockFreeStack<T>::ChainPendingNodes(Node<T>* first, Node<T>* last)
{
	do
	{
		last->next = toBeDeleted;
	}
	while(!CompareAndExchangeWeak<Node<T>*>(&toBeDeleted, last->next, first));
}

template<typename T>
void LockFreeStack<T>::ChainPendingNode(Node<T>* node)
{
	ChainPendingNodes(node, node);
}